The social application of cryptographic technology has been vigorously promoted to ensure the security of communication, and effective cryptographic computation is required more than ever. In such trend, the NTRU cryptosystem proposed in “NTRU: A Ring-Based Public Key Cryptosystem” (Non Patent Document 1) written by Jeffery Hoffstein, Jill Pipher and Joseph H. Silverman attracts attention as a high-speed encryption/decryption computation system with lower memory requirement as compared to the conventional RSA or ElGamal cryptosystem.
(NTRU Cryptosystem)
The NTRU cryptosystem is a public key cryptosystem as follows.
First, a key is created in the following manner. Three integers p, q and N are used as public and domain parameters. Besides, the ring R=Z[X]/(XN−1) is used. Hereinafter, L(a, b) indicates the total set (a subset of R) of an element u∈R having a coefficients equal to 1, b coefficients equal to −1 and the rest 0 for each degree thereof. Parameters df, dg and d are chosen to set Lf=L(df, df+1), Lg=L(dg, dg+1), and Lφ=L(d, d). Two polynomials f∈Lf and g∈Lg are randomly selected such that h=f1 g mod q. Then, the private or secret key is the polynomial f, g, while the public key is the polynomial h.
When the keys have been created, an element m of the subset Lm of R, m∈Lm, is encrypted. A polynomial r∈Lr is randomly selected to compute e=phr+m mod q. Thus, e is output as a ciphertext.
In order to decrypt the ciphertext e to the original plaintext or cleartext m, fe=pgr+fm mod q is computed. Since f, g, r, and m are elements of the subsets Lf, Lg, Lr, and Lm, respectively, fe=pgr+fm. Accordingly, fe(mod p)=m(mod p) can be computed. Also, since the m is an element of the subset Lm, m=m (mod p), and therefore, m can be retrieved.
However, as pointed out in “Lattice Attacks on NTRU”, Eurocrypt '97 Springer Lecture Notes in Computer Science, 1997 (Non Patent Document 2) written by Don Coppersmith and Adi Shamir, there are known a various sorts of attacks against the NTRU cryptosystem. As such, some schemes have been proposed to prevent the attacks, in which some kind of padding is applied to a plaintext before NTRU encryption.
(OAEP+Padding System)
As a padding scheme to secure cryptosystems, for example, the one called OAEP+ is known. The OAEP+ padding was proposed in “OAEP Reconsidered”, Journal of Cryptology 15 (4) (Non Patent Document 3) written by Victor Shoup. The OAEP+ padding is a padding scheme as follows.
First, integers k, k0, and k1 are selected as parameters so as to satisfy k0, +k1≦k≦L, where L is the number of elements in the plaintext space.
Then, n=k−k0−k1 is set.
Let G denote a hash function to map a k-bit string to an n-bit string.
Let H′ be a hash function to map an n+k0-bit string to a k1-bit string.
Let H be a hash function to map an n+k1-bit string to a k0-bit string.
Upon receipt of an n-bit plaintext M, a padder randomly selects a k0-bit string R. Subsequently, the padder computes the exclusive OR s0 of G(R) and each bit of M as well as s1=H′(R∥M) such that s=s0∥s1. Incidentally, the symbol “∥” is used to denote concatenation of bit strings. If t denotes the exclusive OR of H(s) and each bit of R, then w=s∥t. This w is called “OAEP+ padding using the random number R of the plaintext M”. The OAEP+ padding w thus obtained is encrypted (by a cryptosystem not using random numbers), and a ciphertext e is transmitted to a receiver.
The receiver decrypts the ciphertext e to obtain w. After decrypting w, a depadder recovers the plaintext M in the following manner. First, through the use of w=s∥t=s0∥s1∥t, the depadder recovers s0, s1 and t. Then, the depadder computes the exclusive OR of H(s) and each bit of t to recover R. Also, the depadder computes the exclusive OR of G(R) and each bit of s0 to recover M. If s1=H′(R∥M) is satisfied, the depadder outputs M. Otherwise, the depadder rejects the ciphertext e as invalid and outputs ⊥.
The OAEP+ padding, however, is a padding scheme proposed to be applied to cryptosystems not using random numbers the computation of an encryption function. Consequently, if the OAEP+ padding is applied to a cryptosystem using random numbers such as NTRU, security is not always ensured. In addition, when the OAEP+ padding is applied to a cryptosystem using random numbers such as NTRU, not a unique but various application methods may by utilized. Therefore, there is also a problem in that it is not possible to immediately distinguish between secure and insecure padding application methods.
As just described, the OAEP+ padding ensures the security only for cryptosystems not using random numbers. Besides, there have been some OAEP+ or OAEP+ like padding schemes introduced for use with the NTRU cryptosystem using random numbers to ensure the security. Reference may be had to, for example, the following documents:                Joseph H. Silverman, “Plaintext Awareness and the NTRU PKCS”, Technical Report #7 version 2, NTRU Cryptosystems, 1998 (Non Patent Document 4)        Jeffery Hoffstein and Joseph H. Silverman, “Optimizations for NTRU”, Public-key Cryptography and Computational Number Theory (Non Patent Document 5)        Jeffery Hoffstein and Joseph H. Silverman, “Protecting NTRU Against Chosen Ciphertext and Reaction Attacks”, Technical Report #16 version 1, NTRU Cryptosystems, 2000 (Non Patent Document 6)        Phong Q. Nguyen and David Pointcheval, “Analysis and Improvements of NTRU Encryption Paddings”, Crypto 2002 Springer Lecture Notes in Computer Science, 2002 (Non Patent Document 7)        
With all of these padding schemes, attacks against the NTRU cryptosystem has succeeded. The padded version of the NTRU cryptosystem described in Non Patent Document 4 is broken by the algorithm proposed in “A Chosen-Ciphertext Attack against NTRU”, Crypto 2000 Springer Lecture Notes in Computer Science, 2000 (Non Patent Document 8) written by Eliane Jaulmes and Antoine Joux.
Further, the padded version of the NTRU cryptosystem described in Non Patent Documents 5 and 6 is broken by the algorithm proposed in Non Patent Document 7. The padding scheme proposed in Non Patent Document 7 does not protect against attacks presented in “Imperfect Decryption and an Attack on the NTRU Encryption Scheme” (Non Patent Document 9) written by John A. Proos.
There have been proposed padding schemes other than the OAEP+ padding scheme aimed at ensuring the security of cryptosystems using random numbers such as NTRU. However, each padding scheme has a different disadvantage, and the OAEP+ padding is still significant to ensure the security of cryptosystems.
Non Patent Document 1: Jeffery Hoffstein, Jill Pipher and Joseph H. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem”
Non Patent Document 2: “Lattice Attacks on NTRU”, Eurocrypt '97 Springer Lecture Notes in Computer Sciences, 1997
Non Patent Document 3: “OAEP Reconsidered”, Journal of Cryptology 15 (4)
Non Patent Document 4: “Plaintext Awareness and the NTRU PKCS”, Technical Report #7 version 2, NTRU Cryptosystems, 1998
Non Patent Document 5: Jeffery Hoffstein and Joseph H. Silverman, “Optimizations for NTRU”, Public-key Cryptography and Computational Number Theory
Non Patent Document 6: Protecting NTRU Against Chosen Ciphertext and Reaction Attacks”, Technical Report #16 version 1, NTRU Cryptosystems, 2000
Non Patent Document 7: “Analysis and Improvements of NTRU Encryption Paddings”, Crypto 2002 Springer Lecture Notes in Computer Sciences, 2002
Non Patent Document 8: “A Chosen-Ciphertext Attack against NTRU”, Crypto 2000 Springer Lecture Notes in Computer Sciences, 2000
Non Patent Document 9: John A. Proos, “Imperfect Decryption and an Attack on the NTRU Encryption Scheme”